package com.example.code2022;

/**
 * @author: dangwen
 * @createDate: 2022/4/24
 * 74. 搜索二维矩阵
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 */
public class P74 {
    public static void main(String[] args) {
        int[][] ints = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(search(ints, 3));
    }
    // 数组是有序的，递增
    // 核心思想，将二维数组虚拟为一维数组，左右指针，二分查找法
    public static boolean search(int[][] ints, int target){
        int m = ints.length; // 行
        int n = ints[0].length; // 列
        int left = 0; // 左指针
        int right = m * n - 1; // 右指针
        while (left <= right){
            // 中间的点
            int mid = left + (right - left) / 2;
            // 核心：一维数组上的中间的值mid，就等于二维数组中的 mid / n 行, m % n列
            int value = ints[mid / n][mid % n];
            // 如果目标值相等返回true，否则左指针指向mid + 1 或 右指针指向 mid - 1
            if (value == target) {
                return true;
            }else if (value < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}
